package dp.leetcode_63;

public class DP {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if (obstacleGrid == null || obstacleGrid.length == 0 || obstacleGrid[0].length == 0) {
            return 0;
        }
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[][] dp = new int[m][n];
        // 开始位置需要判断是否有障碍物，如果有障碍物可以直接返回 0
        dp[0][0] = obstacleGrid[0][0] == 1 ? 0 : 1;
        // 初始化第 1 列
        for (int i = 1; i < m; i++) {
            // 需要注意：虽然第 1 列的每个位置只依赖其上面的位置，但是如果当前位置[i][0]有障碍物仍然是走不到的
            if (obstacleGrid[i][0] != 1) {
                dp[i][0] = dp[i - 1][0];
            }
        }
        for (int j = 1; j < n; j++) {
            // 同理
            if (obstacleGrid[0][j] != 1) {
                dp[0][j] = dp[0][j - 1];
            }
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; ++j) {
                // 转移方程：dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
                if (obstacleGrid[i][j] != 1) {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
        return dp[m - 1][n - 1];
    }
}
